This disclosure pertains to a method and system for maintaining a graph transitive closure and path structure in a database using database triggers. More particularly, but not by way of limitation, this disclosure relates to firing database triggers when vertices and arcs are added to or deleted from a directed graph modeling a hierarchy to perform a delta operation on the table or tables used to maintain the graph transitive closure and path structure to reduce or possibly eliminate the need to recalculate this information at request time.
Database systems are prevalent in today's computer environment. Many of today's databases have a capability commonly referred to as “triggers.” A database trigger is procedural code that is automatically executed in response to certain events on a particular table or view in a database. The trigger is often used for keeping the integrity of the information in the database. In a simple example, when a new record representing a new worker is added to an employee table, new records should also be added in tables of taxes, vacations and salaries. Database triggers are generally well known in the art and therefore are not explained further here.
A binary relation <R> on a set X is a collection of ordered pairs of elements of X. In other words, it is a subset of the Cartesian product X2=X×X. More generally, a binary relation between two sets A and B is a subset of A×B. The terms dyadic relation and 2-place relation are synonyms for binary relations.
An example is the “divides” relation between the set of prime numbers P and the set of integers Z, in which every prime p is associated with every integer z that is a multiple of p (and not with any integer that is not a multiple of p). In this relation, for instance, the prime 2 is associated with numbers that include −4, 0, 6, 10, but not 1 or 9; and the prime 3 is associated with numbers that include 0, 6, and 9, but not 4 or 13.
Binary relations are used in many branches of mathematics to model concepts like “is greater than”, “is equal to”, and “divides” in arithmetic, “is congruent to” in geometry, “is adjacent to”, “is an ancestor of”, and “is a child of” in graph theory, “is orthogonal to” in linear algebra and many more. The concept of function is defined as a special kind of binary relation. Binary relations are also heavily used in computer science.
A particular kind of binary relation is a transitive relation. A binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c.
The transitive closure <R+> of a binary relation <R> on a set X is the smallest transitive relation on X that contains <R>. If the original relation is transitive, the transitive closure will be that same relation; otherwise, the transitive closure will be a different relation. For example: if X is a set of classes and x<R>y means “x is the parent class of y”, then the transitive closure of <R> on X is the relation <R+> where u<R+>v means: “there is path from u to v”. Simply put, the transitive closure of a digraph is the “reachability” relation of the digraph and a strict partial order.
A Directed Graph or digraph is an ordered pair of two sets. The first set is the set of vertices. The second set is the set of directed edges called arcs. The vertex set is just a collection of the labels for the vertices, a way to tell one vertex from another. The edge set is made up of ordered pairs of vertex labels from the vertex set. A “path” in a digraph is a sequence of vertices from one vertex to another using the arcs. The length of a path is the number of arcs used, or the number of vertices used minus one. A “simple path” cannot visit the same vertex twice. A closed path has the same first and last vertex in the digraph. In a digraph, a “cycle” is a simple closed path.
In a digraph if there is a path from vertex x to vertex y—then x is an ancestor of y. In that respect the Ancestor Descendant Relationship is the transitive closure of the graph's arcs—representing the parent child relationship. Ancestor Descendent Relationships are particularly important in areas of Business Service Management (BSM) and Enterprise Systems Management (ESM) along with many other fields. In BSM and ESM the ancestor descendent relationship is typically used to determine which components of an Information Technology (IT) infrastructure could “impact” (i.e., affect through failure or degradation) other systems or business services that depend upon the component that is not performing to specification. The impact relationship is often maintained in what is called a “service model” and a service model is often represented by a digraph.
Prior art techniques for calculating a directed graph transitive closure exist in many different mathematical formulas and some database vendors provide hierarchical query mechanisms. However, these query mechanisms and formulas require graph traversal upon invocation and accordingly have high time complexities. Therefore, systems and methods are proposed to reduce the time complexities and solve other issues. In one disclosed embodiment, the time required to access the hierarchical data of a service model and dynamically keep the transitive closure data in synch with objects (e.g., IT components, IT services, business services, etc.) modeled via the digraph is reduced.